# 11/100 子串-滑动窗口最大值
# leetcode第239题: https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/11/20
import collections
import json
import heapq
from leetcode import test


def maxSlidingWindow_bf(nums: list[int], k: int) -> list[int]:
    """暴力法, 超时"""
    n = len(nums)
    if n < 2:
        return [nums[0]]
    if n == k:
        return [max(nums)]

    res = []
    for i in range(n - k + 1):
        res.append(max(nums[i: i + k]))
    return res


def maxSlidingWindow_queue(nums: list[int], k: int) -> list[int]:
    """单调队列
    一个单调递减的队列可以保证其首部为最值, 那么可以定义这么一个单调的队列:
    如果一个数字入队的前提是要把队列中小于它的数字全部弹出(pop), 那么这个队列就一定是单调递减的
    arr [2, 1, 4, 2, 3, 2]      arr [2, 1, 4, 2, 3, 2]      arr [2, 1, 4, 2, 3, 2]
         i                              i                              i
    que [2]                     que [2, 1]                  que [4]

    arr [2, 1, 4, 2, 3, 2]      arr [2, 1, 4, 2, 3, 2]      arr [2, 1, 4, 2, 3, 2]
                  i                              i                              i
    que [4, 2]                  que [4, 3]                  que [4, 3, 2]

    这里只要增加判断窗口的位置就符合本题的题意了.
    """
    n = len(nums)
    if n < 2:
        return [nums[0]]
    if n == k:
        return [max(nums)]

    que = collections.deque()
    res = []
    for i in range(n):
        while que and nums[i] > nums[que[-1]]:
            que.pop()
        que.append(i)
        if que[0] == i - k:  # 窗口已经划过队列的头部
            que.popleft()
        if i >= k - 1:
            res.append(nums[que[0]])
    return res


def maxSlidingWindow_heap(nums: list[int], k: int) -> list[int]:
    """优先队列(Priority Queue)
    https://www.bilibili.com/video/BV1AF411G7cA
    优先队列是一种抽象数据结构，支持以“优先级”排序的方式来处理元素。与普通队列不同，优先队列中的元素出队时是根据优先级而非加入队列的顺序。
    每个元素都有一个与之相关的优先级。
    总是按照优先级顺序来出队（通常是从高优先级到低优先级）。
    通常使用 **堆** 来实现高效的优先级管理。

    堆(Heap)
    堆是一种特殊的完全二叉树，分为最大堆（大根堆Max-Heap）和最小堆（小根堆Min-Heap）：
    最大堆：每个父节点的值都大于等于其子节点。
    最小堆：每个父节点的值都小于等于其子节点。
    对于一个完全二叉树来说, 可以使用一个一维数组进行转换. 例如下面的一个大根堆:
            7               对于任意一个节点i来说, 它的两个子节点都可以通过 2i + 1 和 2i + 2 来表示
        5       6           那么对于左侧这个大根堆来说就可以表示为一维数组 arr=[7, 5, 6, 4, 1, 1, 2]
    4     1   1    2
    大(小)根堆可以保证在其对应的一维数组中的第一个元素arr[0]一定是最大(小)的元素.
    如何建立一个数组的大根堆? 有两种常用的方法: 1. 自顶向下建堆 2自下向上建堆
    这里以自顶向下建立一个大根堆为例子, arr = [3, 4, 5, 6, 1, 7, 8]
        3           4        5            5             5           6           6            6
                3         3    4       3     4        6   4       5   4      5     4      5     4
                                6                   3           3          3  1         3  1   7

        6          7              7              8
      5   7     5     6        5     8        5     7
    3  1 4    3  1  4  8     3  1   4  6    3  1   4  6
    """
    n = len(nums)
    # Python 默认的优先队列是小根堆, 如果想要它变为大根堆需要将原数组变为负数
    q = [(-nums[i], i) for i in range(k)]
    heapq.heapify(q)

    ans = [-q[0][0]]
    for i in range(k, n):
        heapq.heappush(q, (-nums[i], i))
        while q[0][1] <= i - k:
            heapq.heappop(q)
        ans.append(-q[0][0])

    return ans


if __name__ == '__main__':
    with open("../data/d_substr2_lc239.data", "r") as file:
        lines = file.read().strip()
        jo = json.loads(lines)

    inp = [{"nums": [1, 3, -1, -3, 5, 3, 6, 7], "k": 3}, {"nums": [2, 1, 4, 2, 3, 2], "k": 3},
           {"nums": [1, -1], "k": 1}, {"nums": [1], "k": 1}, {"nums": jo["nums"], "k": jo["k"]}]
    out = [[3, 3, 5, 5, 6, 7], [4, 4, 4, 3], [1, -1], [1], jo["ans"]]

    # test.test_function(maxSlidingWindow_bf, inp, out)
    test.test_function(maxSlidingWindow_queue, inp, out)
    test.test_function(maxSlidingWindow_heap, inp, out)
